package org.example;


import javafx.util.Pair;
import org.bean.SLRProduction;
import org.example.bean.*;

import java.io.File;
import java.io.FileNotFoundException;
import java.util.*;

public class GrammarParser {
    List<Token> tokenList;

    String res= "";


    Map<Pair<String,String>,List<String>> parseTableMap= new HashMap<>();
    boolean isLL1= true;//是否是LL1文法
    public List<Production> productions;
    List<List<ParseTable>> parseTableList;
    static String start="";


    public String begin="start";
    public Map<String,Production> productionMap;//不会发生在Set查不到元素，并且为first计算做准备
    public GrammarParser(){};
    public static void main(String[] args) {
        File grammarFile = new File("src/main/resources/grammar2.txt"); // 替换为实际的文法文件路径
        try {
            List<Production> productions = parseGrammar(grammarFile);
            for (Production production : productions) {
                System.out.println(production);
            }
        } catch (FileNotFoundException e) {
            e.printStackTrace();
        }
    }

    public static List<Production> parseGrammar(File grammarFile) throws FileNotFoundException {
        Map<String,Set<List<String>>> productions = new HashMap<>();
        Scanner scanner = new Scanner(grammarFile);
        while (scanner.hasNextLine()) {
            String line = scanner.nextLine();
            String[] parts = line.split("::=");

            String left = parts[0].trim();
            String right = parts.length > 1 ? parts[1].trim() : "";
            if(right.isEmpty()){
                right="ε";
            };
            String[] split = right.split(" ");
            List<String> r= new ArrayList<>();
            for (String s : split) {
                r.add(s.trim());
            };
            Set<List<String>> set=new HashSet<>();
            set.add(r);
            if(start.isEmpty()){
                start=left;
            }
            if(productions.get(left)!=null) {
                productions.get(left).addAll(set);
            }
            else {
                productions.put(left,set);
            }
        };


        scanner.close();
        //遍历productions将其转换为List集合
        List<Production> productionList = new ArrayList<>();
        for (Map.Entry<String, Set<List<String>>> pairs: productions.entrySet()) {
            String left = pairs.getKey();
            productionList.add(new Production(left, pairs.getValue()));
        };

        return productionList;
    }

    public  List<SLRProduction> parseGrammar_1(File grammarFile) throws FileNotFoundException {
        List<SLRProduction> productionList = new ArrayList<>();
        Scanner scanner = new Scanner(grammarFile);
        while (scanner.hasNextLine()) {
            String line = scanner.nextLine();
            String[] parts = line.split("::=");

            String left = parts[0].trim();
            String right = parts.length > 1 ? parts[1].trim() : "";
            if(right.isEmpty()){
                right="ε";
            };
            String[] split = right.split(" ");
            List<String> r= new ArrayList<>();
            productionList.add(new SLRProduction(left, Arrays.asList(split)));
        };


        scanner.close();
        return productionList;
    }


    public static void eliminateLeftRecursion(List<Production> productions) {
        Production production2 = productions.get(0);
        productions.remove(0);
        productions.add((production2));


        Set<Production> new_pros = new HashSet<>();
        Map<String,Set<List<String>>> newPros=new HashMap<>();//左部映射右部的产生式表示
        for (Production production : productions) {
            /**
             * 消除间接左递归
             */

            for (Production production1 : productions) {
                if (production1 == production) break;

                List<List<String>> add = new ArrayList<>();
                List<String> del = new ArrayList<>();
                for (List<String> strings : production.getRight()) {

                    if (strings.get(0).equals(production1.getLeft())) {

                        del = strings;

                        for (List<String> stringList : production1.getRight()) {
                            List<String> tmp = new ArrayList<>(strings);
                            tmp.remove(0);
                            tmp.addAll(0, stringList);
                            add.add(tmp);
                        }
                        ;
                    }
                    ;
                }
                ;
                Set<List<String>> right = production.getRight();
                right.remove(del);
                right.addAll(add);
                production.right=right;
            };

            /**
             * 消除直接左递归
             * 1.预处理
             * 2.
             */
            List<List<String>> VTSet = new ArrayList<>();
            for (List<String> strings : production.getRight()) {
                if(!strings.get(0).equals(production.getLeft())){
                    List<String> newRight=new ArrayList<String>(strings);
//                    newRight.add(production.getLeft()+"'");
                    VTSet.add(newRight);
                }
            };

            List<List<String>> add=new ArrayList<>();//新的右部
            List<List<String>> del=new ArrayList<>();//要删除的递归式
            for (List<String> strings : production.getRight()) {
                if(strings.get(0).equals(production.getLeft())){
                    //消除第一个
                    //删除原左部递归式
                    del.add(strings);
                    //添加新右部TE'
                    if(add.isEmpty()) {
                        for (List<String> stringList : VTSet) {
                            List<String> strings1 = new ArrayList<>(stringList);


                            strings1.add(production.getLeft()+"'");
                            add.add(strings1);
                            del.add(stringList);
                        };
                    }
                    //构造新的产生式E'->+TE'
                    strings.remove(0);
                    strings.add(production.getLeft()+"'");
                    if(newPros.containsKey(production.getLeft()+"'")){
                        newPros.get(production.getLeft()+"'").add(strings);
                    }
                    else {
                        Set<List<String>> set = new HashSet<>();
                        set.add(strings);
                        newPros.put(production.getLeft() + "'", set);
                    }

                    //新的产生式添加空
                    List<String> str=new ArrayList<>();
                    str.add("ε");
                    newPros.get(production.getLeft()+"'").add(str);
                };
            };
            //正式添加新右部
            Set<List<String>> r=new HashSet<>(production.getRight());
            production.setRight(r);
            production.right.addAll(add);
            //删除旧左部
            HashSet<List<String>> lists = new HashSet<>();
            r=new HashSet<>(production.getRight());
            production.setRight(r);
            for (List<String> strings : del) {
                production.getRight().remove(strings);
            }

        };
        newPros.forEach((k,v)-> productions.add(new Production(k,v)));
        for (Production production : productions) {
            System.out.println(production);
        }
        }

    public  void getAllFirst(List<Production> productions){
        preGetFist(productions);
        for (Production production : productions) {
            production.first=getFirst(production);
            System.out.println("First["+production.getLeft()+"]:"+production.first);
        }
    }

    public  void getAllFirst_1(List<Production> productions){
        preGetFist(productions);
        for (Production production : productions) {
            production.first=getFirst_1(production);
            System.out.println("First["+production.getLeft()+"]:"+production.first);
        }
    }
    public void getAllFollow(List<Production> productions){
        //如果不把开始文法放在第一会求不出$
        for (Production production : productions) {
            if(production.left.equals(begin)){
                productions.remove(production);
                productions.add(0,production);
                break;
            }
        }
        for (Production production : productions) {
            production.follow=getFollow(production);
//            System.out.println("Follow["+production.getLeft()+"]:"+production.follow);
        }
    }

    public List<String> getFollow(Production production) {
        if(production.follow!=null)return production.follow;
        Set<String> res=new HashSet<>();
//        if(production==productions.get(0))
        if(production.left.equals(begin))
            res.add("$");
        for (Production production1 : productions) {
            for (List<String> oneRight : production1.getRight()) {
                //找到包含这个文法符号的其它产生式
                int idx=0;
                if(oneRight.indexOf(production.getLeft())!=oneRight.size()-1&& oneRight.contains(production.getLeft())){
                    for (String s : oneRight) {
                        if(idx>oneRight.indexOf(production.getLeft())) {
                            if (VN.isVN(s)) {
                                //计算文法符号的后面的文法符号的first
                                List<String> tmp = new ArrayList<>(getFirst(productionMap.get(s)));
                                if (tmp.contains("ε")) {
                                    tmp.remove("ε");
                                    res.addAll(tmp);
                                    if(production1!=production){
                                        tmp = new ArrayList<>(getFollow(production1));
                                        if (tmp.contains("ε")) {
                                            tmp.remove("ε");
                                            res.addAll(tmp);
                                        }
                                    }
                                    res.addAll(tmp);
                                    break;
                                }
                            }
                            else if(VT.isVT(s)){
                                res.add(s);
                                break;
                            }
                        }
                        idx++;
                    }
                }
                else if( oneRight.contains(production.getLeft())){
                    List<String> tmp;
                    if(production!=production1) {
                    tmp=new ArrayList<>(getFollow(production1));
                        res.addAll(tmp);
                    }
                }
            }
        };
        System.out.println("follow["+production.left+"]="+res);
        production.follow=new ArrayList<>(res);//记忆式搜索效率更高
        return production.follow;
//        return new ArrayList<>(res);
    }

    private  void preGetFist(List<Production> productions) {
        this.productions=productions;
        productionMap=new HashMap<>();
        productions.forEach(x->{
            productionMap.put(x.left,x);
        });
    }

    public void setProductions(List<Production> productions){
        begin= productions.get(0).getLeft();
        this.productions=productions;
        productionMap=new HashMap<>();
        productions.forEach(x->{
            productionMap.put(x.left,x);
        });
    }

    public  List<String> getFirst(Production production) {
        if (production.first != null) return production.first;
        //遍历每一个产生式右部
        List<String> res=new ArrayList<>();
        for (List<String> oneRight : production.getRight()) {
            int len=oneRight.size();
            int idx=0;
            //遍历每一个产生式右部序列
            for (String idxS : oneRight) {
                //终结符直接加入first
                if (VT.isVT(idxS)) {

                    res.add(idxS);
                    if(idxS.equals("ε")&&idx!=len-1){
                        res.remove(idxS);
                    }
                    break;
                }
                //非终结符递归计算first
                else if(VN.isVN(idxS)){
                    Set<List<String>> right = productionMap.get(idxS).getRight();
                    res.addAll(getFirst(productionMap.get(idxS)));
                    int haveNull=0;
                    for (List<String> strings : right) {
                        if(strings.size()==1&&strings.get(0).equals("ε")){
                            haveNull=1;
                        }
                    }
                    //还得判断是否含有空
                    if(haveNull==0){
                        break;
                    }
                };
                idx++;
            }
        };
        return res;
    }

    //计算first集之前的方法没有针对含有做递归的文法，毕竟之前还要消除左递归
    public  List<String> getFirst_1(Production production) {
        if (production.first != null) return production.first;
        //遍历每一个产生式右部
        List<String> res=new ArrayList<>();
        for (List<String> oneRight : production.getRight()) {
            int len=oneRight.size();
            int idx=0;
            //遍历每一个产生式右部序列
            for (String idxS : oneRight) {
                int flag=0;
                if(flag==1)break;
                //终结符直接加入first
                if (VT.isVT(idxS)) {

                    res.add(idxS);
                    if(idxS.equals("ε")&&idx!=len-1){
                        res.remove(idxS);
                    }
                    break;
                }
                //非终结符递归计算first
                else if(VN.isVN(idxS)){
                    if (production.left.equals(idxS)&&oneRight.indexOf(idxS)==0) {
                        //左递归文法
                        flag=1;
                        continue;//跳过
                    }
                    Set<List<String>> right = productionMap.get(idxS).getRight();
                    res.addAll(getFirst_1(productionMap.get(idxS)));
                    int haveNull=0;
                    for (List<String> strings : right) {
                        if(strings.size()==1&&strings.get(0).equals("ε")){
                            haveNull=1;
                        }
                    }
                    //还得判断是否含有空
                    if(haveNull==0){
                        break;
                    }
                };
                idx++;
            }
        };
        return res;
    }

    public void initParseTable(List<Production> productions) {
        List<List<ParseTable>> res = new ArrayList<>();
        for (Production production : productions) {
            List<ParseTable> parseTable = getParseTable(production);
            res.add(parseTable);
        }
        parseTableList=res;
        ptParseTable(parseTableList);
    }


    private List<ParseTable> getParseTable(Production production) {
        List<ParseTable> res=new ArrayList<>();
        for (List<String> strings : production.right) {
            int flag = 0;
            //如果右部第一个是产生式的话求它的first和follow
            if (productionMap.containsKey(strings.get(0))) {
                Production pro = productionMap.get(strings.get(0));
                for (String s : pro.first) {
                    ParseTable table=new ParseTable();
                    table.right=new ArrayList<>();
                    if (s.equals("ε")) flag = 1;
                    table.left = production.left;
                    table.right.addAll(strings);
                    table.vt = s;
                    if(parseTableMap.containsKey(new Pair<>(production.left, s))) {
                        System.out.println("存在重复的first follow.分析表存在冲突");
                        isLL1 = false;
                    }
                    else {
                        parseTableMap.put(new Pair<>(production.left, s), new ArrayList<>(strings));
                    }
                    res.add(table);
                }
                ;
                if (flag == 0) {
                    break;
                } else {//包含空使用follow
                    for (String s : pro.follow) {
                        ParseTable table=new ParseTable();
                        table.right=new ArrayList<>();
                        table.left = production.left;
                        table.right.addAll(strings);
                        table.vt = s;
                        if(parseTableMap.containsKey(new Pair<>(production.left, s))) {
                            System.out.println("存在重复的first follow.分析表存在冲突");
                            isLL1 = false;
                        }
                        else {
                            parseTableMap.put(new Pair<>(production.left, s), new ArrayList<>(strings));
                        }
                        res.add(table);
                    }
                }
            }
            //右部直接是终结符
            else {
                if(strings.get(0).equals("ε")) {
                    ParseTable table = new ParseTable();
                    table.right = new ArrayList<>();
                    table.left = production.left;
                    table.right.addAll(strings);
                    table.vt = "ε";
                    if(parseTableMap.containsKey(new Pair<>(production.left, table.vt))) {
                        System.out.println("存在重复的first follow.分析表存在冲突");
                        isLL1 = false;
                    }
                    else {
                        parseTableMap.put(new Pair<>(production.left, table.vt), new ArrayList<>(strings));
                    }
                    res.add(table);
                    for (String s : production.follow) {
                        table=new ParseTable();
                        table.right=new ArrayList<>();
                        table.left = production.left;
                        table.right.addAll(strings);
                        table.vt = s;
                        if(parseTableMap.containsKey(new Pair<>(production.left, s))) {
                            System.out.println("存在重复的first follow.分析表存在冲突");
                            isLL1 = false;
                        }
                        else {
                            parseTableMap.put(new Pair<>(production.left, s), new ArrayList<>(strings));
                        }
                        res.add(table);
                    }
                }
                else {
                    ParseTable table = new ParseTable();
                    table.right = new ArrayList<>();
                    table.left = production.left;
                    table.right.addAll(strings);
                    table.vt = strings.get(0);
                    if(parseTableMap.containsKey(new Pair<>(production.left, table.vt))) {
                        System.out.println("存在重复的first follow.分析表存在冲突");
                        isLL1 = false;
                    }
                    else {
                        parseTableMap.put(new Pair<>(production.left, table.vt), new ArrayList<>(strings));
                    }
                    res.add(table);
                }
            }
        }
            return res;
        }
        ;

    public void ptParseTable(List<List<ParseTable>> parseTableList){
            System.out.println("分析表");
            Set<String> vTSet = new HashSet<>();
            for (Production production : productions) {
                vTSet.addAll(production.first);
                vTSet.addAll(production.follow);
            }
            //打印分析表
            System.out.printf("%-10s","");
            for (String s : vTSet) {
                System.out.printf("%-10s",s);
            };
            System.out.println();
            for (String s : vTSet) {
                System.out.printf("%-10s","-----------");
            };
            System.out.println();

            for (Production production : productions) {
                System.out.printf("%-10s",production.left);
                    for (String s : vTSet) {
                        int flag=0;
                        for (List<ParseTable> parseTable : parseTableList) {
                            for (ParseTable table : parseTable) {
                                if(table.vt.equals(s)&&table.left.equals(production.left)){
                                        System.out.printf("%-10s",table.ptRight());
                                        flag=1;
//                                    }
                                }
                            }

                    };
                        if(flag==0) System.out.printf("%-10s","");
                }
                System.out.println();
            }
            if(isLL1) System.out.println("分析表无冲突，该文法是LL(1)文法");
            else System.out.println("分析表存在冲突，该文法不是LL(1)文法");

        }
    public void setTokenList(List<Token> tokens ){
            tokenList=tokens;
        }
    public boolean match(List<Token>tokens, String left){
        List<String> right;
        if(tokens.get(0).type!=TokenType.ID&&tokens.get(0).type!=TokenType.NUM)
            right=parseTableMap.get(new Pair<>(left, tokens.get(0).value));
        else right=parseTableMap.get(new Pair<>(left, "id"));

        StringBuilder str=new StringBuilder();

        System.out.print("->");
        for (String s : right) {
            if(!s.equals("ε"))
                str.append(s);
        };
        if(res.contains(left)){
            res=res.replace(left,str.toString());
        }
        else
            res = res + str;
        System.out.println(res);

        if(right.size()==1&&right.get(0).equals("ε"))
            return true;
        int idx = 0;
        for (String s : right) {
            String tmp;
            if(tokens.get(idx).type!=TokenType.ID&&tokens.get(0).type!=TokenType.NUM){
                tmp= tokens.get(idx).value;
            }
            else tmp = "id";
            if(s.equals(tmp)||(s.equals("ε")&& tmp.equals("&"))){
                if(tmp.equals("id")){
                    res=res.replace("id",tokens.get(0).value);
                    System.out.println("->"+res);
                }
                tokens.remove(0);
            }
            else if(VN.isVN(s)){
                List<Token> list=tokens;
                if(match(list,s)){
                    tokens=list;
                    idx=0;
                }
                else return false;
            }
            else return false;
        }
        tokens=tokens.subList(idx,tokens.size());
        return true;
    }

    public boolean matchString(String str, String left){
            String tmp=String.valueOf(str.charAt(0));
        List<String> right=parseTableMap.get(new Pair<>(left,tmp ));
        System.out.println("->"+right);
        int idx = 0;
        for (String s : right) {
            if(s.equals(String.valueOf(str.charAt(idx)))){
                System.out.println("->"+s);
                idx++;
                if (idx == str.length())
                    return true;
            }
            else if(VN.isVN(s)){
                String subStr = str.substring(idx);
                if(matchString(subStr,s)){
                    str=subStr;
                    idx=0;
                }
                else return false;
            }
        }
        return false;
    }

    }
